/*
https://leetcode.cn/problems/count-pairs-with-xor-in-a-range/solutions/2044651/tong-ji-yi-huo-zhi-zai-fan-wei-nei-de-sh-cu18/
 */
public class Solution1803 {

    static class Trie{
        Trie[] son=new Trie[2];
        int sum=0;

        void add(int num){
            Trie node=this;
            for (int k=14;k>=0;k--){
                int bit=(num>>k)&1;
                if (node.son[bit]==null){
                    node.son[bit]=new Trie();
                }
                node=node.son[bit];
                node.sum++;
            }
        }

        int get(int num,int x){
            Trie node=this;
            int sum=0;
            for (int k=14;k>=0;k--){
                int r=(num>>k)&1;
                if (((x>>k)&1)!=0){
                    if (node.son[r]!=null){
                        sum+=node.son[r].sum;
                    }
                    if (node.son[r^1]==null){
                        return sum;
                    }
                    node=node.son[r^1];
                }else {
                    if (node.son[r]==null){
                        return sum;
                    }
                    node=node.son[r];
                }
            }
            sum+=node.sum;
            return sum;
        }
    }

    public int countPairs(int[] nums, int low, int high) {
        return f(nums,high)-f(nums,low-1);
    }

    private int f(int[] nums, int x) {
        Trie root=new Trie();
        int res=0;
        for (int i=1;i<nums.length;i++){
            root.add(nums[i-1]);
            res+=root.get(nums[i],x);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1803().countPairs(new int[]{1,4,2,7},2,6));
    }
}
